#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

void generate(int index, int k, vector<int> &cur, vector<int> &input, vector<vector<int> > &subset)
{
    if (cur.size() == k) {
        subset.push_back(cur);
        return;
    }
    if (index >= input.size())
        return;

        cur.push_back(input[index]);
        generate(index+1, k, cur, input, subset);
        cur.pop_back();
        generate(index+1, k, cur, input, subset);
}

int main(int argc, char **argv)
{
    vector<int> input;
    input.push_back(1);
    input.push_back(2);
    input.push_back(3);
    input.push_back(4);
    vector<vector<int> > subset;
    vector<int> cur;
    generate(0, 3, cur, input, subset);
    for (int i = 0; i < subset.size(); i++) {
        for (int j = 0; j < 3; j++) 
            cout << subset[i][j] << " ";
        cout << endl;
    }
    cout << "-----------------Test 1--------------------" << endl;


    cout << "-----------------Test 2--------------------" << endl;


    cout << "-----------------Test 3--------------------" << endl;


    cout << "-----------------Test 4--------------------" << endl;


    cout << "-----------------Test 5--------------------" << endl;



}
